﻿/*
Maximum Sum 
Time Limit:1000MS  Memory Limit:32768K


Description:
A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. 
Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts.
 This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem. 
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1×1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array: 

0  –2  –7   0
9   2  –6   2
-4   1  –4   1
-1   8   0  –2is in the lower-left-hand corner: 
9   2
-4   1
-1   8and has the sum of 15. 

Input:
The input consists of an N×N array of integers. 
The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array.
 This is followed by N^2 integers separated by white-space (newlines and spaces). 
 These N^2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). 
 N may be as large as 100. 
 The numbers in the array will be in the range [-127, 127]. 
Output:
The output is the sum of the maximal sub-rectangle. 
Sample Input:
4
0 -2 -7  0 
9  2 -6  2
-4  1 -4  1
-1 8  0 -2
Sample Output:
15
*/
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
int max_sub_sum(int* a, unsigned n)
{
	int sum = 0, max_sum = INT_MIN;
	for (unsigned i = 0; i < n; ++i)
	{
		if (a[i] > 0)
			sum += a[i];
		else
			sum = a[i];
		if (sum > max_sum)
			max_sum = sum;
	}
	return max_sum;
}
int main()
{
	unsigned n;
	while (cin >> n && n)
	{
		unsigned dim = n * n;
		int* m = new int [dim + 1];
		int max_sum = INT_MIN;
		for (unsigned k = 0; k < dim; ++k)
		{
			cin >> m[k];
			if(m[k]>max_sum)
				max_sum=m[k];
		}
		if(max_sum>0)
			for (unsigned i = 0; i < n; ++i)
			{
				int* sum = new int [n + 1];
				{
					for (unsigned j = 0; j < n; ++j)
						sum[j] = 0;
				}
				{
					for (unsigned k = i; k < n; ++k)
					{
						for (unsigned j = 0; j < n; ++j)
						{
							sum[j] += m[k * n + j];
						}
						int sub_sum = max_sub_sum(sum, n);
						if (sub_sum > max_sum)
							max_sum = sub_sum;
					}
				}		

				delete[]sum;
				sum = NULL;
			}
		delete[]m;
		m = NULL;
		cout << max_sum << endl;
	}
	return EXIT_SUCCESS;
}


